# Definition for a binary tree node.

"""注意这里是一个二叉搜索树，根结点的右子树上所有的点的值都比根结点大，左子树上所有点的值都比根结点的值小
因此分为四种情况，
1、如果两个节点一个值比节点大，一个小，那么二者的公共节点肯定是根结点，
2、如果两个节点中有一个与根结点的值同样大，那么二者的公共节点同样是根结点
3、如果两个节点的值都比根结点小，那么二者的公共节点出现在根结点的左子树中，递归查询
4、如果两个节点的值都比根结点大，那么二者的公共节点出现在根结点的右子树中，递归查询
"""



class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        # m = root.val
        # if (p>m and q<m) or (p==m or q==m) or (p<m and q>m):
        #     return root
        # if p<m and q<m:
        #     return self.lowestCommonAncestor(root.left,p,q)
        # if p>m and q>m:
        #    return self.lowestCommonAncestor(root.right,p,q)

        # while root:
        #     m = root.val
        #     if p < m and q < m:
        #         root = root.left
        #     elif p>m and q>m:
        #         root = root.right
        #     else:
        #         return root

        a = self.help(root, p, q)
        return a

    def help(self, node, p, q):
        if not node:
            return None
        if p == node.val or q == node.val:
            return node
        if (p > node.val and q < node.val) or (p < node.val and q > node.val):
            return node
        if p > node.val and q > node.val:
            a = self.help(node.right, p, q)
        if p < node.val and q < node.val:
            a = self.help(node.left, p, q)
        return a



m1 = TreeNode(6)
m1.left = TreeNode(2)
m1.right = TreeNode(8)
m1.left.left = TreeNode(0)
m1.left.right = TreeNode(4)
m1.right.left = TreeNode(7)
m1.right.right = TreeNode(9)
# m1.right.right = TreeNode(2)
s = Solution()

t = s.lowestCommonAncestor(m1,2,8)
print(t.val)
